package io.tec.cloud.algorithm.c15_v20220711;

import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 83	15_1	15	1	15并查集及其面试题目	547.朋友圈
 * <p>
 * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
 * <p>
 * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 * <p>
 * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
 * <p>
 * 返回矩阵中 省份 的数量。
 * <p>
 * <p>
 * There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
 * <p>
 * A province is a group of directly or indirectly connected cities and no other cities outside of the group.
 * <p>
 * You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
 * <p>
 * Return the total number of provinces.
 * <p>
 * https://leetcode-cn.com/problems/number-of-provinces
 */
public class Code15_1_FriendCircle {

    public static int findCircleNum(int[][] m) {
        int N = m.length;
        List<Integer> list = IntStream.range(0, N).boxed().collect(Collectors.toList());
        UnionFind unionFind = new UnionFind(list);
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                if (m[i][j] == 1) {
                    unionFind.union(i, j);
                }
            }
        }
        return unionFind.sets();
    }

    public static void main(String[] args) {
        int[][] a = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};
        System.out.println(findCircleNum(a));
    }


    static class UnionFind<V> {
        private Map<V, Node<V>> nodeMap = new HashMap<>();
        private Map<Node<V>, Node<V>> parentMap = new HashMap<>();
        private Map<Node<V>, Integer> sizeMap = new HashMap<>();

        public UnionFind(List<V> list) {
            for (V cur : list) {
                Node<V> node = new Node<>(cur);
                nodeMap.put(cur, node);
                parentMap.put(node, node);
                sizeMap.put(node, 1);
            }
        }

        public void union(V v1, V v2) {
            Node<V> f1 = findFather(nodeMap.get(v1));
            Node<V> f2 = findFather(nodeMap.get(v2));
            if (f1 != f2) {
                Integer f1Size = sizeMap.get(f1);
                Integer f2Size = sizeMap.get(f2);
                // 小挂大
                Node large = f1Size >= f2Size ? f1 : f2;
                Node small = large == f1 ? f2 : f1;
                parentMap.put(small, large);
                sizeMap.put(large, f1Size + f2Size);
                sizeMap.remove(small);
            }
        }

        public int sets() {
            return sizeMap.size();
        }

        // 扁平化
        private Node<V> findFather(Node<V> cur) {
            Stack<Node<V>> path = new Stack<>();
            while (cur != parentMap.get(cur)) {
                path.push(cur);
                cur = parentMap.get(cur);
            }
            while (!path.isEmpty()) {
                parentMap.put(path.pop(), cur);
            }
            return cur;
        }
    }

    static class Node<V> {
        V v;

        public Node(V value) {
            this.v = value;
        }
    }
}
